package com.zhj.leetcode;

import java.util.ArrayList;
import java.util.List;

/**
 * 力扣78 子集
 */
public class Test78 {
    public static void main(String[] args) {
        int[] nums = {1,2,3};
        List<List<Integer>> subset = getSubset3(nums);
        for (List<Integer> list : subset) {
            System.out.print("[ ");
            for (Integer num : list) {
                System.out.print(num + "\t");
            }
            System.out.print(" ]");
            System.out.println();
        }
    }

    /**
     * 扩展法
     * @param nums
     * @return
     */
    public static List<List<Integer>> getSubset(int[] nums) {
        if (nums == null) {
            return null;
        }
        // 空集合是所有集合的子集
        List<List<Integer>> result = new ArrayList<>();
        result.add(new ArrayList<>());
        for (int num : nums) {
            // 子集
            List<List<Integer>> subset = new ArrayList<>();
            for (List<Integer> list : result) {
                List<Integer> temp = new ArrayList<>(list);
                temp.add(num);
                subset.add(temp);
            }
            // 将子集添加到结果集中
            for (List<Integer> list : subset) {
                result.add(list);
            }
        }
        return result;
    }

    /**
     * 回溯
     * @param nums
     * @return
     */
    public static List<List<Integer>> getSubset2(int[] nums) {
        if (nums == null) {
            return null;
        }
        // 空集合是所有集合的子集
        List<List<Integer>> result = new ArrayList<>();
        result.add(new ArrayList<>());
        for (int i = 1; i <= nums.length; i++) {
            backtracking(nums, result, i, 0, new ArrayList<>());
        }
        return result;
    }

    /**
     * 回溯法
     * @param nums
     * @param result
     * @param length
     * @param index
     * @param subset
     * @return
     */
    private static void backtracking(int[] nums, List<List<Integer>> result, int length, int index, List<Integer> subset) {
        if (subset.size() == length) {
            List<Integer> temp = new ArrayList<>(subset);
            result.add(temp);
            return;
        }
        for (int i = index; i < nums.length; i++) {
            subset.add(nums[i]);
            backtracking(nums, result, length, i+1, subset);
            subset.remove(subset.size()-1);
        }
    }

    /**
     * DFS
     * @param nums
     * @return
     */
    public static List<List<Integer>> getSubset3(int[] nums) {
        if (nums == null) {
            return null;
        }
        // 空集合是所有集合的子集
        List<List<Integer>> result = new ArrayList<>();
        dfs(nums, result, 0, new ArrayList<>());
        return result;
    }

    private static void dfs(int[] nums, List<List<Integer>> result, int index, List<Integer> subset) {
        result.add(new ArrayList<>(subset));
        if (index == nums.length) {
            return;
        }
        for (int i = index; i < nums.length; i++) {
            subset.add(nums[i]);
            dfs(nums, result, i+1, subset);
            subset.remove(subset.size()-1);
        }
    }
}
